package bank;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _17TelNumCom {
    public static List<String> letterCombinations(String digits) {
        int len = digits.length();
        List<String> resLetters = new ArrayList<>();
        if (len == 0) {
            return resLetters;
        }
        Map<Character,String> hashMap = new HashMap<>(8);
        hashMap.put('2',"abc");
        hashMap.put('3',"def");
        hashMap.put('4',"ghi");
        hashMap.put('5',"jkl");
        hashMap.put('6',"mno");
        hashMap.put('7',"pqrs");
        hashMap.put('8',"tuv");
        hashMap.put('9',"wxyz");

        //构造了HashMap后，需要找到题设字符串：digit中每个数字对应的字符
        //可以遍历digit，找到7和9的个数，和剩下数字的个数，可以算出链表总长度
        //链表长度等于pow(3,剩下数字个数）*pow(4,总个数-剩下数字个数)
        //这也是该算法的时间复杂度

        //构造resLetters链表：重点！！！
        //思路：递归方法！
        backtrack(resLetters,hashMap,digits,0,new StringBuilder());
        return resLetters;
    }
    private static void backtrack(List<String> combinations,Map<Character,String> phoneMap,String digits,int index,StringBuilder combination){
        if(index == digits.length()){
            //这里的List集合里泛型是String类，所以StringBuilder类型变量需要加toString方法
            combinations.add(combination.toString());
        }else {
            //将digit位置处的字符找出来
            char digit = digits.charAt(index);
            //找到key对应的value
            String letters = phoneMap.get(digit);
            //该value对应的字符串长度
            int lettersCount = letters.length();
            //应用递归
            for(int i = 0;i < lettersCount;i++){
                combination.append(letters.charAt(i));
                backtrack(combinations,phoneMap,digits,index+1,combination);
                //每次递归处理完成后，combination的当前位置字符需要清除，给下一个字符留出空间
                //StringBuilder类的重要函数deleteCharAt(int);
                combination.deleteCharAt(index);
            }
        }
    }
}
